Data compression is an extremely useful tool for storing and transmitting large amounts of data. For example, the time required to transmit an image, such as a facsimile transmission of a document, is reduced drastically when compression is used to decrease the number of bits required to transmit the image. Many different data compression techniques exist in the prior art.
Every compression system is associated with a corresponding decompression system. The implementation of a decompression system can normally be inferred from the compression system. The algorithm used by the compression system to effectuate encoding must be either transmitted as part of the compressed document or inferable by the decompression system.
More specifically, in entropy coding, a sequence of "input" symbols&lt;t.sub.1 t.sub.2 t.sub.3 . . . , t.sub.m &gt;, which are typically data samples or quantized error values, can be replaced deterministically with a sequence of "output.revreaction. codewords&lt;s.sub.1, s.sub.2, s.sub.3, . . . , s.sub.n &gt;as a function of time: EQU f(t)=(s)=&lt;s.sub.1, s.sub.2, . . . s.sub.n &gt;
such that a deterministic inverse (reconstruction) function exists: EQU f.sup.-1 (s)=(t), for all {t}, {s}=f({t})
This type of entropy code f may be built from a set of instantaneous production rules. The result of applying each of these rules is the generation of an ordered sequence of zero or more output tokens. However, the number of output tokens is usually one or more.
In some compression systems, an input file or set of data is translated into a sequence of decisions under the direction of a decision model. Each decision has an associated likelihood, and based on this likelihood, an output code is generated and appended to the compressed file. To implement these encoding systems, the compression systems have three parts: a decision model, a probability estimation method and a bit-stream generator. The decision model receives the input data and translates the data into a set of decisions which the compression system uses to encode the data. The probability estimation method is the procedure for developing the estimate for the likelihood of each decision. The bit-stream generator performs the final bit-stream encoding to generate the output code that is the compressed data set or compressed file. Compression can effectively occur in either or both the decision model and the probability estimation method.
One compression technique widely employed is arithmetic coding. Arithmetic coding maps a string of data (i.e., a "message") to a code string in such a way that the original message can be recovered from the code string wherein the encoding and decoding algorithms perform arithmetic operations on the code string. For a discussion on arithmetic coding see, Glenn G. Langdon, Jr., "An Introduction to Arithmetic Coding", IBM Journal of Research and Development, vol. 28, no. 2, (March 1984).
In arithmetic coding, the code representative of a message is represented by an interval of numbers between 0 and 1. As the number of symbols in the message increases, the interval representing it becomes smaller and the number of bits needed to specify that interval increases. Initially, the interval for the message is between zero and one [0,1). As each symbol of the message is processed, the interval is narrowed in accordance with the symbol probability.
For example, referring to FIG. 1a, the symbols (in this instance, text) z, y, x, w, v, u are assigned the probabilities 0.2, 0.3, 0.1, 0.2, 0.1, 0.1. The probabilities are then mapped to the range of [0,1.0) resulting in the ranges identified in FIG. 1a. Referring to FIG. 1a, the symbol z is allocated the range [0,0.2) reflecting the probability of 0.2 and the symbol u is allocated the range of 0.9, 1.0) reflecting the high end of the probability range of symbols and the u probability of 0.1.
In order for compression to be possible, the symbols which occur more frequently are assigned a greater probability value. Once the probability ranges are allocated, the symbols may be encoded for compression. The initial range or interval is set to [0,1). After the occurrence of the first symbol of the message to be compressed, the range is narrowed in proportion to that symbol's probability. Referring to FIG. 1a, the range [0,1) is first illustrated. After the occurrence of the symbol y, the range is decreased to a new interval of size proportional to the probability of y. In other words, instead of the range or interval being set to its initial values, the range is set according to the probability of the symbol which just occurred. Since the probability of y is 0.3 and has a range of [0.2, 0.5), the updated range from which the encoding occurs is [0.2, 0.5), such that the probability of occurrence of the next symbol includes the influence of the probabilities of the symbols which came before it (i.e., y). Thus, all of the probabilities for the symbols total a range from 0.2 to 0.5 instead of 0 to 1 as before the occurrence of the symbol y. Similarly, after the occurrence of the next symbol z, which has the probability of 0.2 and the range [0, 0.2) the interval is decreased in proportion to the z probability to [0.2, 0.26), such that the range of probabilities for the next symbol is taken from the interval 0.2 to 0.26, with the influence of both the previous y and z symbols taken into account.
In decoding, since the size of the interval used in the encoding process is indicative of the probability range of a symbol in group of symbols, the symbols can be easily extracted, using the ranges for each symbol that were utilized in encoding. For example, if the final interval was [0.23, 0.236), one can determine that the first symbol is y because the final interval lies completely within the range of y [0.2, 0.5). Using the same process as the encoder, after seeing y, the initial interval [0, 1) is updated to be [0.2, 0.5) and the updated range of a [0.2, 0.26) encompasses the final interval [0.23, 0.236). This process continues until all symbols are decoded.
A binary arithmetic coder is one type of an arithmetic coding system. In a binary arithmetic coding system, the selection of a symbol from a set of symbols can be encoded as a sequence of binary decisions. An example of a binary arithmetic coder is the "Q-coder" developed at International Business Machines, Armonk, N.Y. The Q-coder utilizes fixed precision arithmetic and a renormalization process wherein the code string and interval are renormalized as necessary in order to maintain the values within the bounds allowed by fixed-precision representation. In addition, to avoid the need to perform a multiplication operation to scale the interval to reflect the coding of a symbol, an approximation is utilized in place of the multiplication. In the prior art, a compressed bit-stream is often characterized as being sent over a lossless bandwidth limited channel. The compressed bit-stream is then received and decoded. However, channels, in reality, are usually not lossless. Therefore, some form of error correction encoding and some sort of channel modulation are performed. In the prior art, these are separate operations.
Another commonly used set of codes are referred to as constrained channel codes. One type of channel codes are run length limited (RLL) codes. RLL codes are often used in the disk drive industry, particularly when raw data is being written to a magnetic track. Codes having very similar characteristics to RLL codes are also used for digital magnetic tape, CD-ROMs, optical disks, and even fiber optic cables. In these cases, a group of arbitrary binary digits is converted to a longer sequence of binary digits with some constraints on the pattern of allowable one and zero bits. For the basic RLL codes, the constraint is that a `1` bit is always followed by at least d `0` bits and at most k `0` bits. Codes following such a format are commonly referred to as RLL (d,k) codes. For instance, a code having a 1 followed by at least 1 `0` bit and at most 7 `0` bits is referred to as an RLL (1,7) code. Such a code is described in U.S. Pat. No. 4,413,251, entitled "Method and Apparatus for Generating a Noiseless Sliding Block Code for a (1,7) Channel with Rate 2/3", Adler et al. In Adler, reference is also made to (1,8) and (2,7) codes. A widely used RLL code is called Modified Frequency Modulation (MFM). MFM is a RLL (1,3) code and, therefore, creates a sequence where every `1` is followed by at least one zero and at most three zeros. Use of these constrained channel codes is universal and actually allows more information to be stored on a disk.
Channel codes being used in channel modulation produce outputs at a fixed rate. In other words, an encoder implementing such a code receives a fixed number of arbitrary input bits and produces a fixed larger number of constrained bits. Because the prior art is limited to outputting only fixed length output bit streams, these channel codes do not use all possible constrained sequences. Thus, it is advantageous to provide codes that make use of more output code streams while being technological feasible.
The functions of data compression and channel modulation are both required in the performance of some applications. However, these functions are implemented with separate units in the prior art. This requires extra hardware and may require extra resources. Thus, it would be advantageous to implement the functions of data compression and channel coding in the same functional unit simultaneously to reduce the hardware required.
In addition to being compressed, data is often encoded to allow error correction after transmission over a noisy channel. Noise occurs in virtually any digital channel, including satellite links and disk drives. In error correction coding, a previously arbitrary bit stream is expanded in a way which meets constraints that make it possible to detect and correct errors in the bit stream. This is similar to the coding done for the run length limited channels, although the constraint is different. The functions of error correction and data compression are also usually implemented by separate functional units. Thus, it is advantageous to have the data compression and error correction performed simultaneously by the same functional unit as a means to reduce the required hardware.
As will be shown, the present invention provides a binary entropy coder that uses a decision model which produces decisions which are always two-valued (i.e., yes or no). The present invention also employs output tokens which are not fixed-length bit strings. In particular, the present invention encodes most decisions with less than one bit.
The present invention also provides a finite state machine to perform channel coding. Another finite state machine of the present invention performs error correction coding. It is also possible to perform channel coding and compression with one finite state machine.